#!/usr/bin/env python3

"""
Given an array nums of n integers and an integer target, find three integers in nums such that sum is closest to target. 

Return the sum of the three integers. You may assume that each input would have exactly one solution

Example:
Input: nums = [-1, 2, 1, -4], and target = 1
Output is 2: (-1 + 2 + 1) = 2
"""

class Solution:
    def three_sum_closest(self, nums, target):
        nums.sort()
        closest = None
        for index, val in enumerate(nums):
            if index == len(nums) - 2:
                break
            remain = target - val
            two_closest = self.two_sum_closest(nums, remain, index + 1)
            maybe_closest = two_closest + val
            if closest is None or abs(maybe_closest - target) < abs(closest - target):
                closest = maybe_closest
        return closest
            

    def two_sum_closest(self, nums, target, start):
        _start = start
        _end = len(nums) - 1
        _last_sum = None
        while _start < _end:
            start_val = nums[_start]
            end_val = nums[_end]
            _sum = start_val + end_val
            if _last_sum is None or abs(_last_sum - target) > abs(_sum - target):
                _last_sum = _sum
            if _sum < target:
                _start += 1
            elif _sum > target:
                _end -= 1
            else:
                return target
        return _last_sum

if __name__ == '__main__':
    solution = Solution()
    result = solution.three_sum_closest([-55, -24, -18, -11, -7, -3, 4, 5, 6, 9, 11, 23, 33], 0)
    print(str(result))
#    result = solution.three_sum_closest([1, 2, 5, 10, 11], 12)
#    result = solution.three_sum_closest([-1, 2, 1, -4], 1)
